package first.niuke.midding;

import java.util.*;

/**
 * @ClassName NC14
 * @description:
 * @author: 荣燊
 * @create: 2021-04-09 11:30
 **/
public class NC14 {
    // 按之字形顺序打印二叉树，用res的大小来判断奇偶层
    public static void main(String[] args) {

    }

    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    }

    public static ArrayList<ArrayList<Integer>> zigzagLevelOrder (TreeNode root) {
        // write code here
        //双端队列Deque
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();

        if (root != null) {
            deque.add(root);
        }

        while (!deque.isEmpty()) {
//            ArrayList<Integer> list = new ArrayList<>();
            //为什么不使用上面的写法而使用下面的写法
            Deque<Integer> list = new LinkedList<>();
            //用res.size()就可以判断奇、偶数层
            for (int i=deque.size(); i>0; i--) {
                TreeNode node = deque.poll();
                if (res.size() % 2 == 0) {
                    list.addLast(node.val);
                } else {
                    list.addFirst(node.val);
                }
                if (node.left != null) {
                    deque.add(node.left);
                }
                if (node.right != null) {
                    deque.add(node.right);
                }
            }

            ArrayList<Integer> list1 = new ArrayList<>();
            while (!list.isEmpty()) {
                list1.add(list.pollFirst());
            }
            res.add(list1);
        }
        return res;
    }
}
